package com.ma.array.binary;

/**
 * @ClassName Solution410
 * @Author: mayongqiang
 * @DATE 2022/3/23 14:12
 * @Description: 分割数组的最大值
 */
public class Solution410 {
    /*
    给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
    设计一个算法使得这 m 个子数组各自和的最大值最小。 找到这个最小的最大值
        输入：nums = [7,2,5,10,8], m = 2
        输出：18
        解释：一共有四种方法将 nums 分割为 2 个子数组。
            其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
            因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
     */

    public static void main(String[] args) {
        int[] nums = {7, 2, 5, 10, 8};
        int m = 2;
        System.out.println(splitArray(nums, m));
    }

    //要求的是 子数组和的最大值  规定了子数组个数   ---->  设计函数  自变量为 子数组和的最大值  返回值为 子数组个数
    public static int splitArray(int[] nums, int m) {
        // 一般搜索空间都是左闭右开的 所以hi要+1
        int lo = getMax(nums), hi = getSum(nums) + 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            // 返回值为 子数组和为mid时 子数组的个数(最少)
            int n = split(nums, mid);
            if (n == m) {
                //收缩右边界
                hi = mid;
            } else if (n < m) { // 最大子数组和的值为mid时子数组的个数小于规定的子数组的个数 需要减小最大子数组的和
                //  最大子数组和的上限高了  最大子数组和的值越大  返回的子数组个数越小
                hi = mid;
            } else if (n > m) {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private static int method1(int[] nums, int m) {
        // 要寻找的是符合条件的某个 子数组和的最大值
        // 转换为  在 子数组和最大值允许的范围内  调整子数组和的最大值 让其对应的子数组个数 = m
        //子数组和最大值的 最小值=数组中最大的元素    最大值=原数组和
        int lo = getMax(nums), hi = getSum(nums);
        for (int max = lo; max <= hi; max++) {
            // 代表 子数组和最大值为max时 至少可以分割为 n个子数组
            // 计算
            int n = split(nums, max);
            if (n <= m) {
                return max;
            }
        }
        return -1;
    }

    /*
     * 在每个子数组和不超过max的情况下，至少可以分割成几个子数组
     * */
    public static int split(int[] nums, int max) {
        int count = 1;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum + nums[i] > max) {
                count++;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
        }
        return count;
    }

    public static int getMax(int[] nums) {
        int res = 0;
        for (int n : nums) {
            res = Math.max(res, n);
        }
        return res;
    }

    public static int getSum(int[] nums) {
        int res = 0;
        for (int n : nums) {
            res += n;
        }
        return res;
    }

}
